home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / exarray.com / EXTARRAY.DOC < prev    next >
Encoding:
Text File  |  1989-08-19  |  6.1 KB  |  137 lines
  1. (*********************************************************************)
  2.  
  3.      The ExtendedArray Object  -- written by Eric C. Wentz
  4.  
  5.                        Last Mod. Date: August 19, 1989
  6.  
  7.                        CompuServe  72070,1015
  8.  
  9.                        2374 Antiqua Court
  10.                        Reston, Va.  22091
  11.  
  12.                        1-703-860-3807 (before 11pm Eastern)
  13.  
  14. (*********************************************************************)
  15.  
  16. Important Note 1:
  17.  
  18.           These units will not compile without several units
  19.           included in GENERI.ARC -- Available in the OOP library
  20.           in the BPROGA area om compuserve.
  21.  
  22.           Specifically, units GenArray, FlexPntr, and SrtFuncs.
  23.  
  24. (*********************************************************************)
  25.  
  26.  UNIT DEPENDENCIES
  27.  
  28.  
  29.               XGlobals
  30.                 /|\
  31.    FlexPntr    / | \    GenArray
  32.         \     /  |  \     /
  33.          \   /   |   \   /
  34.           \ /    |    \ /
  35.        ExtBuff   |  XManager
  36.          \       |       /
  37.           \      |      /
  38.            \     |     /
  39.    FlexPntr \    |    /
  40.         |  \ \   |   /
  41.         |   \ \  |  /
  42.         |    \ \ | /
  43.         |     \ \|/
  44.         |    X_Table
  45.         |     /
  46.         |    /
  47.         |   / FlexPntr
  48.         |  /    |
  49.        ExtArray |   SrtFuncs
  50.          |   \  |  /    |
  51.          |    \ | /     |
  52.          |     \|/      |
  53.          |   XGenHeap   |
  54.          |         \    |
  55.          |          \   |
  56.          |           \  |
  57.          |            XHeaps
  58.          |                |
  59.          |                |
  60.          |                |
  61.          |                |
  62.        ExtTest          Test
  63.  
  64.  
  65. (*********************************************************************)
  66.  
  67. COMMENTS:
  68.  
  69.          The ExtendedArray was intended to be a general-purpose Generic
  70.          array of (up to) DiskSize proportions.  As it has met some
  71.          goals and failed (miserably) at others, I changed the name
  72.          from the original (VirtualArray) to more accurately reflect
  73.          the nature of the Object.  I am also continuing work on a
  74.          more general-purpose implementation, which will keep the
  75.          designation VirtualArray, but may end up limited (by DOS)
  76.          to a "meager" 32 Mbytes.  I present the ExtendedArray, warts
  77.          and all, because it DOES have some good uses after all.  It
  78.          is a very good solution for those times where a MaxArray is
  79.          not quite big enough (but almost), and has been designed
  80.          with almost one-for-one code compatibility with MaxArray
  81.          applications (initialization is the ONLY exception). It will
  82.          also find use in those programs which use a MaxArray, but
  83.          would benefit by "freeing-up" a little more RAM for other uses.
  84.  
  85.          The ExtendedArray, while an interesting exercise, has proved
  86.          to have some serious problems.  While it has achieved the
  87.          original goal of being unlimited (other than by Disk Size and
  88.          NOT by the DOS File limit of 32 Mbytes), it has done so at a
  89.          very large cost in performance -- at least for very large
  90.          applications.  For those uses which do not exceed 1 or 2
  91.          MBytes, it should prove a more than adequate performer for
  92.          most tasks.  For those applications which require primarily
  93.          sequential access, such as a Gargantuan stack for example,
  94.          the ExtendedArray will provide very satisfactory performance
  95.          at ANY size.  The performance problems arise under 2 conditions.
  96.          The first is when the application requires frequent random
  97.          access to array elements.  The second arises when the entire
  98.          array must be accessed sparsely (as in the standard Heap
  99.          operation SiftDown).  Both of these requirements cause a
  100.          condition best described as "Disk Thrashing", wherein large
  101.          chunks of the array ("Lobes") must be continuosly swapped
  102.          in and out of RAM.  Both of these situations defeat any
  103.          prioritizing scheme I can imagine (or implement!).
  104.  
  105.          Speaking of the prioritization scheme, it occurs to me that
  106.          I have failed to document it.  It is optimized for the
  107.          sequential access case (since I gave up early on anything else),
  108.          and simply increases the priority of a Lobe each time it must
  109.          be loaded from it's Disk file. Thus, at all times the 7 Lobes
  110.          which have been most frequently loaded from disk will be in
  111.          RAM, along with the last Lobe accessed, regardless of it's
  112.          current priority.  It may be interesting to experiment with
  113.          increasing the priority of the last accessed Lobe to 1 greater
  114.          than the former highest, but I do not see how this would help
  115.          the Random access problem.  I have stored priorities as LongInts,
  116.          so I don't think it will be possible to overrun the highest
  117.          theoretical priority (not in MY lifetime anyway!), and have
  118.          therefore made no effort to ever reset the priorities to
  119.          lower values.  Be warned: If you plan an application which
  120.          will access a Lobe more than 2147483647 times, you will need to
  121.          address this (Heh, heh).
  122.  
  123.          It may be possible to achieve very good sort times by
  124.          implementing a kind of MergeSort, working on whole Lobes
  125.          and merging them into another buffer which would then
  126.          write to disk.  This will probably be quite complex, and
  127.          require some extensive work in unit ExtArray. It may
  128.          even require a whole auxiliary file structure based around
  129.          another instance of the ExtendedTable Object, which means
  130.          (as with all MergeSorts), considerable extra overhead.
  131.          Due to complexity, overhead, and shear cowardice, I have
  132.          made no attempt at this idea.  If you do and get it working,
  133.          please let me know!  For that matter, if you want to discuss
  134.          the idea, drop me a note -- maybe we can work it out together!
  135.  
  136. (*********************************************************************)
  137. (*********************************************************************)